\bigskip
\bigskip
{\magonebf 5.10 Node partitions (node\_partition)}

An instance of the data type $node\_partition$ is a partition of the nodes
of some graph $G$.


\def\name{$node\_partition$}
\def\type{node\_partition}

\bigskip
{\bf 1. Creation of a node partition}


\create P (G)

creates an instance \var\ of type \name\ containing for every node $v$ in 
$G$ a block $\{v\}$. 



\bigskip
{\bf 2. \operations}

\+\cleartabs & \hskip 1.5truecm & \hskip 6.5truecm &\cr
\+\op bool  same\_block   {node\ v,\ node\ w}  
                             {returns true if $v$ and $w$ belong to the }
\+\nop                       {same block of \var.}
\smallskip
\+\op void union\_blocks {node\ v,\ node\ w} 
                             {unites the blocks of \var\ containing nodes}
\+\nop                       {$v$ and $w$.}
\smallskip
\+\op node find {node\ v}    {returns a canonical representative node of}
\+\nop                       {the block that contains node $v$.}
\smallskip


\bigskip
{\bf 3. Implementation}

A node partition for a graph $G$ is implemented by a combination of a 
partition $P$ and a node array of $partition\_item$ associating with 
each node in $G$ a partition item in $P$. Initialization takes linear time,
union\_blocks takes time $O(1)$ (worst-case), and same\_block and find take 
time $O(\alpha(n))$ (amortized).  The space requirement is $O(n)$, where $n$ 
is the number of nodes of $G$.

\vfill\eject

